//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
//
//
//
// 示例 1:
//
//
//
//
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
//
//
// 示例 2：
//
//
//
//
//输入： heights = [2,4]
//输出： 4
//
//
//
// 提示：
//
//
// 1 <= heights.length <=10⁵
// 0 <= heights[i] <= 10⁴
//
//
// Related Topics 栈 数组与矩阵 单调栈 👍 2403 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function largestRectangleArea(heights: number[]): number {

    //? 加0避免一直单调递增造成结果为0的情况 以及最后一个元素才递减的情况（即没有计算最后一个元素能构成的面积） 一直单调递减则没这情况
    heights.push(0);
    const length: number = heights.length;
    //? 栈底->栈顶：严格单调递增
    const stack: number[] = [];
    stack.push(0);
    let resMax: number = 0;
    for (let i = 1; i < length; i++) {
        let top = stack[stack.length - 1];
        //? 满足单调递增
        if (heights[top] < heights[i]) {
            stack.push(i);
        } else if (heights[top] === heights[i]) {
            //? 相同去重 栈里只留一个最新的下标 这段可以不要
            stack.pop();
            stack.push(i);
        } else {
            //? 不满足单调递增 计算前面的最大面积(当前元素也就充当长度计算) 即每根柱子高度乘以宽度
            while (stack.length > 0 && heights[top] > heights[i]) {
                let mid = stack.pop();
                //? 这里赋值-1的情况是 前面的都比当前元素大时 当前mid元素的高度可以乘以前面的总宽度
                /*
                流程是：
                1.自己 x1
                2.第二个 x2
                3.第三个 x3
                ...
                 */
                let left = stack.length > 0 ? stack[stack.length - 1] : -1;
                //? 宽度
                let w = i - left - 1;
                //? 高度
                let h = heights[mid];
                resMax = Math.max(resMax, w * h);
                top = stack[stack.length - 1];
            }
            stack.push(i);
        }
    }
    return resMax;
};
//leetcode submit region end(Prohibit modification and deletion)
